package com.example.demo.algorithms;

import lombok.extern.slf4j.Slf4j;
import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * <p>Description: 有序集合链表</p>
 *
 * @author Eric Lee
 * @version v1.0.0
 * @since 2021/2/28 19:26
 **/
@Slf4j
public class SortedList {

    @Test
    public void test() {
        Integer[] s1 = {1, 3, 6, 7, 9};  // 有序，不重复
        Integer[] s2 = {2, 3, 7, 8, 9};   // 有序，不重复
        List<Integer> S1 = new ArrayList<Integer>(Arrays.asList(s1));
        List<Integer> S2 = new ArrayList<Integer>(Arrays.asList(s2));
        sortedSubtractionAB(S1, S2);
        sortedUnionAB(S1, S2);

    }

    // 求A和B的并集
    public void sortedUnionAB(List<Integer> a, List<Integer> b) {
        List<Integer> S1 = new ArrayList<>(a);
        List<Integer> S2 = new ArrayList<>(b);
        List<Integer> U = new ArrayList<>();
        while (!S1.isEmpty() && !S2.isEmpty()) {
            if (S1.get(0) < S2.get(0)) {
                U.add(S1.get(0));
                S1.remove(0);
            } else {
                U.add(S2.get(0));
                S2.remove(0);
            }
        }
        while (!S1.isEmpty()) {
            U.add(S1.get(0));
            S1.remove(0);
        }
        while (!S2.isEmpty()) {
            U.add(S2.get(0));
            S2.remove(0);
        }
        log.info("并集：{}", U);
    }

    public void sortedSubtractionAB(List<Integer> a, List<Integer> b) {
        List<Integer> I = new ArrayList<>();   // 交集
        List<Integer> Sa = new ArrayList<>();    // A\B差集
        int count = 0;
        while (!a.isEmpty() && !b.isEmpty()) {
            if (a.get(0) < b.get(0)) {
                Sa.add(a.get(0));  // a中存在，b中不存在的差集
                a.remove(0);
            } else if (a.get(0) == b.get(0)) {
                I.add(a.get(0));  // a和b的交集
                a.remove(0);
            } else {
                b.remove(0);
            }
            count++;
        }
        log.info("交集：{}", I);
        log.info("A\\B差集：{}", Sa);
    }
}
